package leetcode101.double_pointer;

import java.util.HashMap;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code2
 * @Description Minimum Window Substring
 * Given two strings s and t, return the minimum window in s which will contain all the characters in t.
 * If there is no such window in s that covers all characters in t, return the empty string "".
 *
 * Note that If there is such a window, it is guaranteed that there will always be only one unique minimum window in s.
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-03-26 19:34
 */
public class Code2 {

    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        minWindow(s, t);
    }


    public static String minWindow(String s, String t) {
        /*
        边界值处理
         */
        if (t == null || s == null || t.length() > s.length()) {
            return "";
        }
        if (t.equals(s)) {
            return s;
        }

        int position = 0; // position代表了每次找窗口的位置
        String res = s; // 返回结果默认设置为s
        boolean flag = false; // flag为true代表找到了最小的

        HashMap<Character, Integer> table = new HashMap<>(); // 创建t字符串的字典

        for (int i = 0; i < t.length(); i++) {
            if (table.get(t.charAt(i)) == null) {
                table.put(t.charAt(i), 1);
            } else {
                table.put(t.charAt(i), table.get(t.charAt(i)) + 1);
            }
        }

        while (position < s.length()) {
            if (table.get(s.charAt(position)) != null) {
                String temp = charCheck(s, t, position, table);
                if ("".equals(temp)) {
                    position++;
                    continue;
                }
                if (temp.length() <= res.length()) {
                    res = temp;
                    flag = true;
                }
            }
            position++;
        }
        return flag ? res : "";
    }

    /*
    如果匹配成功了返回匹配成功的串
    如果失败了返回空串
     */
    public static String charCheck(String s, String t, int position, HashMap<Character, Integer> table) {

        HashMap<Character, Integer> charTable = (HashMap<Character, Integer>) table.clone();
        int counter = t.length();
        int right = position;

        while(counter > 0 && right < s.length()) {
            if (charTable.get(s.charAt(right)) != null && charTable.get(s.charAt(right)) != 0) {

                charTable.put(s.charAt(right), charTable.get(s.charAt(right)) - 1);
                counter--;
            }
            right++;
        }

        return  counter == 0 ? s.substring(position, right) : "";
    }
}
/*
要点是用到了双指针和hash表
使用双指针确定窗口的范围
使用hash表去判断是否窗口中包含了所有待匹配的字符
 */